//@safe:
import std.stdio;
import std.array;
import std.conv;
import std.range;
import std.typecons;
import std.process;
import std.math;
import std.regex;
import std.algorithm;
import std.exception;
import std.random;

/+

dmd -O -release -inline -m64 crubic.d

+/

const int CSIZE = 2;

string[][string] cubeOpers(){
	// cube facets rotations
	string[][string] ret;
	ret[`front-to-right`] = ["410-411 100-110 501-500 311-301", "000 001 011 010"]; // turn front to right+
	ret[`back-to-right`]  = ["400-401 101-111 511-510 310-300", "201 200 210 211"]; // turn back to right+
	ret[`left-to-front`]  = ["400-410 000-010 500-510 211-201", "300 301 311 310"]; // turn left to front+
	ret[`right-to-front`] = ["401-411 001-011 501-511 210-200", "100 110 111 101"]; // turn right to front+  
    ret[`top-to-right`]   = ["000-001 100-101 200-201 300-301", "410 411 401 400"]; // turn top to right+
    ret[`bottom-to-right`]= ["010-011 110-111 210-211 310-311", "500 501 511 510"]; // turn bottom to right+
    
    ret[`front-back-to-right`] = ret[`front-to-right`] ~ ret[`back-to-right`];//+
    ret[`left-right-to-front`] = ret[`left-to-front`] ~ ret[`right-to-front`];//+
    ret[`top-bottom-to-right`] = ret[`top-to-right`] ~ ret[`bottom-to-right`];//+
	return ret; 
}

enum CUBE_OPERS = cubeOpers();

struct CUBE{
// layout: side1 - lines, then side2 - lines, side3, ...
/*

400 401
410 411

000 001  100 101  200 201  300 301
010 011  110 111  210 211  310 311

500 501
510 511

	side layout:
	4
	0123
	5

*/
  byte[CSIZE][CSIZE][6] vals;
  ref byte byStr(string pos){
  	return vals[ pos[0]-'0' ][ pos[1]-'0' ][ pos[2]-'0' ];
  }


	byte[][] readState(string opers){
		byte[][] ret;
		foreach(op; split(opers)){
			string[] ends;
			foreach(m; match(op, regex(r"\d\d\d"))){
				ends ~= m.hit;
	 	    }
			static if (CSIZE!=2){
				assert(false);
			}
			enforce(ends.length<3);
			if( ends.length==1 ){
				ret ~= [ byStr(ends[0]) ];	
			}else{
			  	ret ~= [ byStr(ends[0]), byStr(ends[1]) ];
			}
		}
		return ret;
	}

	void writeState(string opers, byte[][] data){
		foreach(i, op; split(opers)){
			string[] ends;
			foreach(m; match(op, regex(r"\d\d\d"))){
				ends ~= m.hit;
	 	    }
			static if (CSIZE!=2){
				assert(false);
			}
			enforce(data[i].length<3);
			byStr(ends[0]) = data[i][0];
			if( data[i].length==2 ){
			  byStr(ends[1]) = data[i][1];
			}
		}
	}
	
	void rotateRev(string opers){
		auto state = readState(opers);
		bringToFront(state[0..1], state[1..$]);
		writeState(opers, state);
	}
	void rotateFwd(string opers){
		auto state = readState(opers);
		bringToFront(state[0..$-1], state[$-1..$]);
		writeState(opers, state);
	}
	
	void operExec(string oper){
		scope(failure) writeln("oper err",oper);
		if( oper[0]=='-' ){
			operExecRev(oper[1..$]);
		}else{
			enforce(oper in CUBE_OPERS);
			foreach( s ; CUBE_OPERS[oper] ){
				rotateFwd(s);
			}
		}
	}
	void operExecRev(string oper){
		enforce(oper in CUBE_OPERS);
		foreach( s ; CUBE_OPERS[oper] ){
			rotateRev(s);
		}
	}
	
	void randomize(ref Random rnd, string[] opers, int count){
		foreach(i; 0..count){
			string op = opers[uniform(0,$,rnd)];
			//writeln("randomizing - ", op);
			operExec( op );			
		}
	}
	
	int[] diffCount(const ref CUBE other){
	  int[] diffs;	
      foreach( side; 0..6 ){
        int c=0;
	    foreach( line; 0..CSIZE ){
			foreach( i; 0..CSIZE ){
				if( vals[side][line][i] != other.vals[side][line][i] ){
					c++;
				}				
			}
		}
	    diffs ~= c;
	  }
      return diffs;
	}
	
	void orFrom(const ref CUBE other){
        foreach( side; 0..6 ){
    	  foreach( line; 0..CSIZE ){
  			foreach( i; 0..CSIZE ){
  				//auto oldc = vals[side][line][i];
  				cellOrFrom( vals[side][line][i],  other.vals[side][line][i] );
  				/+
  				if( oldc!=vals[side][line][i] ){
  					writeln("cell changed ",side," ",line," ",i);
  				}
  				+/
  			  }
  			}
    	  }
	}
	
	void cellOrFrom(ref byte myCell, byte otherCell){
		if( myCell!=otherCell ){
			if( myCell==0 ){
				myCell = otherCell;
			}else{
				enforce(otherCell==0,"myCell "~myCell~" otherCell "~ otherCell);
			}
		}
	}
	
	int sideSameValsMaxCount(int side){
		int[6] countsByVal;
		foreach( line; 0..CSIZE ){
			foreach( i; 0..CSIZE ){
				int val = vals[side][line][i];
				countsByVal[val] ++;				
			}
		}
		return reduce!max(countsByVal);
		
	}
	
	int[] complexDiff(const ref CUBE reference){
		int[] diffs = diffCount(reference);
		foreach(side; 0..6){
			diffs ~= CSIZE * CSIZE - sideSameValsMaxCount(side);
		}
		return diffs;
	}
	
	string bestOperToward(int[] delegate(CUBE c) diffFunc, string[] opers, bool[CUBE] avoidStates){
		CUBE ctmp;
		string best;
		int[] bestDiff = [int.max];
		foreach(op; opers){
			ctmp = this;
			ctmp.operExec(op);
			if( ctmp!=this && ctmp !in avoidStates ){
				//int diff = reduce!("a + b")(ctmp.complexDiff(other));
				int[] diff = diffFunc(ctmp);
				//writeln("after op ",op, " diff ",diff);
				//print_cube(ctmp);
				if( diff<bestDiff ){
					bestDiff=diff;
					best = op;
				}
			}
		}
		return best;
	}
	
};

void println_cube(ref const CUBE c){
	print_cube(c);
	writeln();
}


void print_cube(ref const CUBE c){
  foreach( line; 0..CSIZE ){
    foreach( side; 0..6 ){
        //int base = side*CSIZE*CSIZE + line*CSIZE;
        static if( CSIZE==3 ){
          printf("%2x %2x %2x  ", c.vals[side][line][0], (c.vals[side][line][1]), (c.vals[side][line][2]));
        }else if( CSIZE==2 ){
          printf("%1x%1x ", (c.vals[side][line][0]), (c.vals[side][line][1]) );
          if( side==3 ) printf("T");
          if( side==4 ) printf("B");
        }
    }
    printf("\n");
  }
}

CUBE mkCube(){
  CUBE c;

  foreach( side; 0..6 ){
    foreach( line; 0..CSIZE ){
        foreach( row; 0..CSIZE ){
            c.vals[side][line][row] = cast(byte)(side);
        }
    }
  }
  return c;
}

CUBE mkRndCube(){
  CUBE c;

  foreach( side; 0..6 ){
    foreach( line; 0..CSIZE ){
        foreach( row; 0..CSIZE ){
            c.vals[side][line][row] = cast(byte)uniform(1,7);
        }
    }
  }
  return c;
}

void testOpers(){
	CUBE cube = mkRndCube();
	CUBE orig = cube;
	cube.operExec(`top-bottom-to-right`);
	cube.operExec(`right-to-front`);
	cube.operExecRev(`top-bottom-to-right`);
	cube.operExec(`front-to-right`);
	enforce(cube==orig);
	
	cube.operExec(`left-to-front`);
	cube.operExec(`top-bottom-to-right`);
	cube.operExecRev(`front-to-right`);
	cube.operExecRev(`top-bottom-to-right`);
	enforce(cube==orig);

	cube.operExec(`back-to-right`);
	cube.operExec(`left-right-to-front`);
	cube.operExecRev(`top-to-right`);
	cube.operExecRev(`left-right-to-front`);
	enforce(cube==orig);

	cube.operExec(`back-to-right`);
	cube.operExec(`top-bottom-to-right`);
	cube.operExec(`left-to-front`);
	cube.operExecRev(`top-bottom-to-right`);
	enforce(cube==orig);
	
	cube.operExec(`bottom-to-right`);
	cube.operExecRev(`front-back-to-right`);
	cube.operExec(`right-to-front`);
	cube.operExec(`front-back-to-right`);
	enforce(cube==orig);

	cube.operExec(`bottom-to-right`);
	cube.operExec(`-front-back-to-right`);
	cube.operExec(`right-to-front`);
	cube.operExec(`front-back-to-right`);
	enforce(cube==orig);
}

void target(string[] opers, CUBE cbwork, int[] delegate(CUBE c) diffFunc){
	bool[CUBE] prevStates;
	foreach( i; 0..1150 ){
		if( diffFunc(cbwork)[0]==0 ){
			writeln("target reached steps=",i);
			return;
		}

	    string opMk = cbwork.bestOperToward(diffFunc,opers,prevStates);
	    prevStates[cbwork]=true;
	    cbwork.operExec(opMk);
	    writeln();
		writeln("after op ",opMk, " new diff=", diffFunc(cbwork));
		print_cube(cbwork);
	}
	
	
}

/*
void solidOpersSolve(){
	string[] solidOpers = [
		`front-back-to-right`, `-front-back-to-right`,
		`left-right-to-front`, `-left-right-to-front`,
		`top-bottom-to-right`, `-top-bottom-to-right`,
	];
	
	CUBE cb = mkRndCube();
	print_cube(cb);
 	cb  = mkCube();
    writefln("inited:");
    print_cube(cb);
    
    //auto rnd0 = MinstdRand0(1);
    Mt19937 rndgen;
    rndgen.seed(unpredictableSeed);
    //rndgen.seed(1);
    CUBE cbwork = mkCube();
    cbwork.randomize(rndgen, solidOpers, 55);
    //cbwork.operExec(`front-back-to-right`);
    //cbwork.operExec(`front-back-to-right`);
    
	writeln("solid randomoved diff=", cbwork.diffCount(cb));
    print_cube(cbwork);
    
    target(solidOpers, cbwork, cb);

}
*/

void targetPredicates(){
	string[] allCubeOpers = cubeOpers().keys;
	foreach(op; allCubeOpers){
		allCubeOpers ~= "-" ~ op;
	}
	writeln(allCubeOpers.length, ' ',allCubeOpers);

    CUBE cb;
    cb.vals[0][0][0]=1;
    cb.vals[0][0][1]=1;
    cb.vals[0][1][0]=1;
    cb.vals[0][1][1]=1;

	//cb.vals[1][0][0]=2;
	cb.vals[1][0][1]=2;
	//cb.vals[1][1][0]=2;
	cb.vals[1][1][1]=2;
	print_cube(cb);
	
	bool[CUBE] preTarget1;
	foreach(op1; allCubeOpers){
		CUBE ctmp1 = cb;
		ctmp1.operExec(op1);
  		preTarget1[ctmp1]=true;
  	}
	
	bool[CUBE] preTarget2;
 	foreach(op1; allCubeOpers){
		foreach(op2; allCubeOpers){
			CUBE ctmp = cb;
			ctmp.operExec(op1);
			ctmp.operExec(op2);
	  		preTarget2[ctmp]=true;
		}
	}
	//preTarget.remove( cb );
	writeln("Pre-target1 cubes: ", preTarget1.length);
	writeln("Pre-target2 cubes: ", preTarget2.length);
    //print_cube(preTarget);

	CUBE cbwork = cb;
	Mt19937 rndgen;
	cbwork.randomize(rndgen, allCubeOpers, 7);
	writeln("rnd cube:");
    print_cube(cbwork);
    //cbwork.operExec(`-bottom-to-right`);
    //cbwork.operExec(`-bottom-to-right`);
    //print_cube(cbwork);
    
    auto distFunc = (CUBE cube){
    	int[] diffs1;
    	foreach(pt; preTarget1.keys){
			diffs1 ~= reduce!("a + b")(cube.diffCount(pt));    		
    	}

		int[] diffs2;
		foreach(pt; preTarget2.keys){
			diffs2 ~= reduce!("a + b")(cube.diffCount(pt));    		
		}
		
    	return [reduce!("a + b")(cube.diffCount(cb)) ? 1 : 0, 
    		reduce!min(diffs1),
			reduce!min(diffs2),
    		];
    	//return 
        // [reduce!("a + b")(cube.diffCount(cb)), reduce!("a + b")(cube.diffCount(preTarget))]; 
    };
    
    target(allCubeOpers, cbwork, distFunc );

	
}

 
void countStates(){
	// cube 2x2 1 facet count states 4 cells =5670, 3 cells = 1512, 2 cells = 252, 1 cell =24
	
	string[] allCubeOpers = cubeOpers().keys;
	foreach(op; allCubeOpers){
		allCubeOpers ~= "-" ~ op;
	}

    CUBE cb;
    cb.vals[0][0][0]=1;
    cb.vals[0][0][1]=1;
    //cb.vals[0][1][0]=1;
    //cb.vals[0][1][1]=1;
	print_cube(cb);

	CUBE cbwork = cb;
	Mt19937 rndgen;
	bool[CUBE] states;
	foreach(i; 0..158_000 ){
	  cbwork.randomize(rndgen, allCubeOpers, 1);
	  states[cbwork]=true;
    }
    writeln("counts states ",states.length);
}

void main(){
	testOpers();
	// old_targetOpmimFunc()
	//countStates();
	targetPredicates();


}

void old_targetOpmimFunc(){
	//solidOpersSolve();
	
	string[] allCubeOpers = cubeOpers().keys;
	foreach(op; allCubeOpers){
		allCubeOpers ~= "-" ~ op;
	}
	writeln(allCubeOpers.length, ' ',allCubeOpers);

	
	CUBE cb = mkRndCube();
	print_cube(cb);
 	cb  = mkCube();
    writefln("inited:");
    print_cube(cb);
    
    //auto rnd0 = MinstdRand0(1);
    Mt19937 rndgen;
    //rndgen.seed(unpredictableSeed);
    CUBE cbwork = mkCube();
    //cbwork.randomize(rndgen, allCubeOpers, 3);

    cbwork.operExec(`back-to-right`);
    cbwork.operExec(`top-bottom-to-right`);
    cbwork.operExec(`-back-to-right`);
    
	writeln("solid randomoved diff=", cbwork.complexDiff(cb));
    print_cube(cbwork);
    
//    target(allCubeOpers, cbwork, cb);
	
}

void experim(){
	/*
	foreach(dc; [217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256]){
		writefln("    server  dc%sf   dc%s.4shared.com:8080 check",dc,dc);
	}
	*/
}